package org.geekbang.time.mathbasicthought.lesson11_width_first_traversal;

import java.util.*;

/**
 * 社交网络中的好友关系
 */
public class BFSTest {
    public static void main(String[] args) {
        Node[] userNodes = insert(10, 5);
        System.out.println(Arrays.asList(userNodes).toString());
        bfs(userNodes, 6);
    }

    static class Node {
        // 节点名称，这里使用用户id
        public int userId;
        // 使用哈希映射存放相连的朋友节点
        public HashSet<Integer> friends;
        // 用于存放和给定的用户，是几度好友
        public int degree;

        public Node(int id) {
            userId = id;
            friends = new HashSet<>();
            degree = 0;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "userId=" + userId +
                    ", friends=" + friends +
                    ", degree=" + degree +
                    '}';
        }
    }

    public static Node[] insert(int userNum, int relationNum) {
        Node[] userNodes = new Node[userNum];

        // 生成所有表示用户的节点
        for (int i = 0; i < userNum; i++) {
            userNodes[i] = new Node(i);
        }

        Random random = new Random();
        // 生成所有表示好友关系的边
        for (int i = 0; i < relationNum; i++) {
            int friendAId = random.nextInt(userNum);
            int friendBId = random.nextInt(userNum);

            // 自己不能是自己的好友，如果生成的两个好友id相同，跳过
            if (friendAId == friendBId)
                continue;

            Node friendA = userNodes[friendAId];
            Node friendB = userNodes[friendBId];

            friendA.friends.add(friendBId);
            friendB.friends.add(friendAId);
        }

        return userNodes;
    }

    /**
     * 通过广度优先搜索，查找好友
     *
     * @param userNodes 用户的节点
     * @param userId    给定的用户id，我们要为这个用户查找好友
     */
    public static void bfs(Node[] userNodes, int userId) {
        // avoid array index out of
        if (userId > userNodes.length)
            return;

        // 用于广度优先搜索的队列
        Queue<Integer> queue = new LinkedList<>();

        // 放入起始节点
        queue.offer(userId);

        // 存放已经被访问过的节点，防止回路
        HashSet<Integer> visited = new HashSet<>();
        visited.add(userId);

        while (!queue.isEmpty()) {
            // 拿出队列头部的第一个元素
            Integer currentUserId = queue.poll();

            if (userNodes[currentUserId] == null)
                continue;

            // 遍历刚刚拿出的这个结点的所有直接连接结点，并加入队列尾部
            for (Integer friendId : userNodes[currentUserId].friends) {
                if (userNodes[friendId] == null)
                    continue;

                if (visited.contains(friendId))
                    continue;

                queue.offer(friendId);
                // 记录已经访问过的结点
                visited.add(friendId);

                // 好友度数是当前好友的度数再加1
                userNodes[friendId].degree = userNodes[currentUserId].degree + 1;
                System.out.println(String.format("\t%d度好友: %d", userNodes[friendId].degree, friendId));
            }
        }
    }
}
